#任务7: 搜索（线性和二分查找）、排序（冒泡排序、选择排序）、

# 线性查找
def linear_search(list, target):
    for i in range(len(list)):
        if list[i] == target:
            return i
    return None


numbers = [10, 20, 30, 40, 50, 60, 70, 80, 90]
print(linear_search(numbers, 1))


# 二分查找
def binary_search(list, target):
    low = 0
    high = len(list) - 1

    while low <= high:
        mid = (low + high) // 2
        guess = list[mid]
        if guess == target:
            return mid
        elif guess > target:
            high = mid - 1
        else:
            low = mid + 1
    return None


numbers = [10, 20, 30, 40, 50, 60, 70, 80, 90]
print(binary_search(numbers, 50))

#排序，1.冒泡排序
def bubble_sort(lst):
    n = len(lst)
    for i in range(n):
        for j in range(0,n-i-1):
            if lst[j]>lst[j+1]:
                lst[j],lst[j+1] = lst[j+1],lst[j]  #交互位置
    return lst
lst = [64, 34, 25, 12, 22, 11, 90]
print(bubble_sort(lst))  # 输出：[11, 12, 22, 25, 34, 64, 90]
#gif演示图片如下
# https://img-blog.csdnimg.cn/2021080211550283.gif
#2.选择排序
def selection_sort(lst):
    for i in range(len(lst)):
        min_index =i
        for j in range (i+1,len(lst)):
            if lst[j]<lst[min_index]:
                min_indx = j
                lst[i],lst[min_index]=lst[min_index],lst[i]#交互位置
    return lst
lst = [64, 34, 25, 12, 22, 11, 90]
print(selection_sort(lst))  # 输出：[11, 12, 22, 25, 34, 64, 90]
#gif
# https://img-blog.csdnimg.cn/20210711213326712.gif
#这个地址可以查看所有gif图
# https://blog.csdn.net/yjh_dream/article/details/81232851?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522169675700416800226582094%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=169675700416800226582094&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduend~default-1-81232851-null-null.142^v95^insert_down28v1&utm_term=%E9%80%89%E6%8B%A9%E6%8E%92%E5%BA%8Fgif%E5%9B%BE&spm=1018.2226.3001.4187
